package apsp;


public class AllPairsShortestPath {
	
	public static final int MAX = Integer.MAX_VALUE;
	
	
	
	public static void floydWarshall(int[][] adjacency) {
		int n = adjacency.length;
		int[][][] D = new int[adjacency.length+1][adjacency.length][adjacency.length];
		int[][][] pi = new int[adjacency.length+1][adjacency.length][adjacency.length];
		
		D[0] = adjacency;
		
		//初始化pi[0]
		for(int i = 0; i < pi[0].length; i++) {
			for(int j = 0; j < pi[0][i].length; j++) {
				if(i != j && adjacency[i][j] < MAX)
					pi[0][i][j] = i+1;
				else
					pi[0][i][j] = 0;
			}
		}
		
		
		
		for(int k = 1; k <= n; k++) {  
			for(int i = 0; i < n; i++) {
				for(int j = 0; j < n; j++) {
					//System.out.println("k = " + k + "   i=" + i + "   j=" +j);
					if(D[k-1][i][j] > D[k-1][i][k-1] + D[k-1][k-1][j]) {
						if(D[k-1][i][k-1] != MAX && D[k-1][k-1][j] != MAX) {
							D[k][i][j] = D[k-1][i][k-1] + D[k-1][k-1][j];
							pi[k][i][j] = pi[k-1][k-1][j];
						}
						else {
							D[k][i][j] = D[k-1][i][j];
							pi[k][i][j] = pi[k-1][i][j];
						}
					} else {
						D[k][i][j] = D[k-1][i][j];
						pi[k][i][j] = pi[k-1][i][j];
					}
				}
			}
		}
		//打印出D[0]...D[n]
		for(int i = 0; i < D.length; i++) {
			for(int j = 0; j < D[i].length; j++) {
				for(int k = 0; k < D[i][j].length; k++)
					System.out.print(D[i][j][k] + "\t");
				System.out.println();
			}
			System.out.println();
		}
		System.out.println("\n\n\n\nPI：");
		
		//打印出pi[0]..pi[n]
		for(int i = 0; i < pi.length; i++) {
			for(int j = 0; j < pi[i].length; j++) {
				for(int k = 0; k < pi[i][j].length; k++)
					System.out.print(pi[i][j][k] + "\t");
				System.out.println();
			}
			System.out.println();
		}
		
	}
	
	
	public static void main(String[] args) {
		int[][] adjacency ={
				{0, 3,  8,   MAX, -4},
				{MAX, 0, MAX,   1,   7},
				{MAX, 4, 0, MAX, MAX},
				{2, MAX,   -5,   0, MAX},
				{MAX, MAX, MAX, 6,  0}
		};
		floydWarshall(adjacency);
	}
}
